# 归并排序
def merge_sort(num_list):
    length = len(num_list)

    # 递归终止退出条件
    if length <= 1:
        return num_list

    # 拆分
    mid = length // 2 # /2 普通除法，结果为浮点数 //2 整除
    left_l = merge_sort(num_list[:mid])  # 对左侧的列表进行排序   1.递归中，左侧数据拆分完才执行下面的
    right_l = merge_sort(num_list[mid:])  # 对右侧的列表进行排序  2.递归中，右侧数据拆分完才执行下面的

    # 3.递归中，上面拆分完了才执行这下面的代码。最初都拆成了一个元素
    # merge 合并操作
    # 初始化两个指针p, q 初始位置为起始位置，初始化一个临时数组temp_list
    p, q, temp_list = 0, 0, list()
    len_left, len_right = len(left_l), len(right_l)  # 计算当前被合并的列表的长度

    # 对左右两个数组进行排序，用临时数组存储
    while len_left > p and len_right > q:
        if left_l[p] <= right_l[q]:
            temp_list.append(left_l[p])
            p += 1
        else:
            temp_list.append(right_l[q])
            q += 1
    # 如果left 和 right 的长度不相等（ len_left >  and len_right > q才排序，q、p达到一方的长度后就停止了，会有一方长的没排），
    # 把长的部分直接追加到列表中
    temp_list += left_l[p:]
    temp_list += right_l[q:]

    return temp_list


if __name__ == '__main__':
    num_list = [8, 4, 5, 7, 1, 3, 6, 2]
    new_list = merge_sort(num_list)
    for k, v in enumerate(new_list):
        num_list[k] = v
    print('num_list:', num_list)
